package bintree;

import java.util.NoSuchElementException;

/**
 * 基于int的二分搜索树
 */
public class MyBinSearchTree {
    private int size;//个数
    private Node root;//树根

    //添加add
    public void add(int val){
        root = add(root, val);
    }

    /*
     *  向当前以root为根的BST中插入一个新元素val，返回插入后的树根
     */
    //add重载
    private Node add(Node root, int val) {
        if(root == null){
            root = new Node(val);
            size ++;
        }
        if(val < root.val){
            //小于根值，左子树
            root.left = add(root.left, val);
        }
        if(val > root.val){
            //小于根值，左子树
            root.right = add(root.right, val);
        }
        return root;
    }

    public boolean contains(int val){
        return contains(root, val);
    }

    /**
     * 判断以当前root为根的BST中是否包含指定值val，存在返回true，否则返回false
     */
    private boolean contains(Node root, int val) {
        if(root == null){
            return false;
        }
        if(root.val == val){
            return true;
        }else if(val < root.val){
            //小于根值，左子树
            return  contains(root.left, val);
        }else{
            //小于根值，左子树
            return  contains(root.right, val);
        }
    }

    //找最小值
    public int findMin() {
        if (size == 0) {
            throw new NoSuchElementException("bst is empty!no element!");
        }

        return min(this.root).val;
    }

    //找最大值
    public int findMxn() {
        if (size == 0) {
            throw new NoSuchElementException("bst is empty!no element!");
        }

        return mxn(this.root).val;
    }
    /**
     * 找出当前root根节点的最大值节点
     */
    private Node mxn(Node root) {
        if(root.right == null){
            return root;
        }
        return mxn(root.right);
    }

    /**
     * 找出当前root根节点的最小值节点
     */
    private Node min(Node root) {
        if(root.left == null){
            // 这个节点就是第一个碰到的左子树为空的结点
            return root;
        }
        return min(root.left);
    }

    //删除最小值，返回删除节点值
    public int removeMin(){
        if(size == 0){
            throw new NoSuchElementException("bst is empty!cannot remove");
        }
        Node minNode = min(root);
        root = removerMin(root);//因为removerMin会返回删除后的删除根节点，更新一下root。
        return minNode.val;
    }
    //删除最大值，返回删除节点值
    public int removeMxn(){
        if(size == 0){
            throw new NoSuchElementException("bst is empty!cannot remove");
        }
        Node mxnNode = mxn(root);
        root = removerMxn(root);//因为removerMxn会返回删除后的删除根节点，更新一下root。
        return mxnNode.val;
    }

    //删除任意节点值
    public void remove(int val){
        if(size == 0){
            throw new NoSuchElementException("bst is empty!cannot remove");
        }
        root =  remove(root, val);
    }

    /**
     * 在当前以root为根的BST中删除值为val的节点，
     * 返回删除后的新树根节点
     */
    private Node remove(Node root, int val) {
        if(root == null){
            //将树中所有节点全部遍历一遍以后还是没找到值为val的节点，节点根本不存在！
            throw new NoSuchElementException("bst has not this node!");
        }else if(val < root.val){
            //在左子树中寻找并删除
            root.left = remove(root.left, val);
            return root;
        }else if(val > root.val){
            //在右子树中寻找并删除
            root.right = remove(root.right, val);
            return root;
        }else{
            //树不为空，且root.val == val;
            //当前的root就是待删除的节点
            if(root.left == null){
                //只存在右子树，且删除的是根节点，是最小值。
                Node right = root.right;//保存待删除节点的右子树
                root.right = root = null;//断开连接和置空
                size --;
                return right;
            }
            if(root.right == null){
                //只存在左子树，且删除的是根节点，是最大值。
                Node left = root.left;//保存待删除节点的左子树
                root.left = root = null;//断开连接和置空
                size --;
                return left;
            }
            //这个待删除的节点左右子树都不为空，Hibbard Deletion
            //找到当前root的后继节点，也就是右子树中的最小值节点。
            Node successor = min(root.right);//保存最小值节点,就是以后的树根节点了
            //1.先在右子树中删除这个节点，最小值
            successor.right = removerMin(root.right);
            //2.连接root.left
            successor.left = root.left;
            //断开和置空待删除的节点
            root.left = root.right = root = null;
            return successor;

        }

    }

    /**
     * 传入一颗以root为根的BST，就能删除其中的最小值，返回删除后的树根节点
     */
    private Node removerMin(Node root) {
        if(root.left == null){
            Node right = root.right;
            root.left = root.right = root = null;//统统置空断开连接
            size --;
            return right;
        }
        root.left = removerMin(root.left);
        return root;
    }

    /**
     * 传入一颗以root为根的BST，就能删除其中的最大值，返回删除后的树根节点
     */
    private Node removerMxn(Node root) {
        if(root.right == null){
            Node left = root.left;
            root.left = root.right = root = null;//统统置空断开连接
            size --;
            return left;
        }
        root.right = removerMxn(root.right);
        return root;
    }

    //打印
    @Override
    public String toString() {
        StringBuilder str = new StringBuilder();
        generateBSTString(root, 0, str);
        return str.toString();
    }

    /**
     * 按照先序遍历的方式，将BST的节点值存入到str之中
     * @param root:根
     * @param height :当前树的高度
     * @param str：zfc
     */
    private void generateBSTString(Node root, int height, StringBuilder str) {
        if(root == null){
            str.append(generateHeightStr(height)).append("NULL\n");
            return;//记得结束
        }
        //打印根 ：根的高低， 根的值， 换行
        str.append(generateHeightStr(height)).append(root.val).append("\n");
        generateBSTString(root.left, height + 1, str);//左子树
        generateBSTString(root.right,  height+ 1, str);//右子树
    }

    /**
     *  按照当前节点的高度打印 --
     * @param height 高度值
     */
    private String generateHeightStr(int height) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < height; i++) {
            sb.append("--");
        }
        return sb.toString();
    }
}

//创建数的节点
class Node{
    int val;//保存的值
    Node left;//左孩子地址
    Node right;//右孩子地址
    //构造方法
    public Node(int val) {
        this.val = val;
    }
}